\documentclass[a4paper,10pt]{article}
\usepackage[spanish,activeacute]{babel}
\usepackage{amsmath}

\newcommand{\produccion}[2]{\ensuremath{#1 \rightarrow #2}}
\newcommand{\produce}[2]{\ensuremath{#1 \Rightarrow^* #2}}
\newcommand{\produceD}[2]{\ensuremath{#1 \Rightarrow^*_R #2}}
\newcommand{\produccionD}[2]{\ensuremath{#1 \rightarrow_R #2}}
\newcommand{\Gramatica}{\ensuremath{<V_n, V_T, P, S>}}
\newcommand{\Automata}{\ensuremath{<Q, \Sigma, \delta, q_0, F>}}
\newcommand{\AutomataPrima}{\ensuremath{<Q', \Sigma, \delta', q_0', F'>}}
\newcommand{\MaquinaTuring}{\ensuremath{<Q, \Sigma, \Gamma, \delta, q_0, B, F>}}
\newcommand{\MaquinaTuringPrima}{\ensuremath{<Q', \Sigma, \Gamma, \delta', q_0', B, F'>}}
\newcommand{\AutomataPila}{\ensuremath{<Q, \Sigma, \Gamma, \delta, q_0, Z_0, F>}}
\newcommand{\AutomataPilaPrima}{\ensuremath{<Q', \Sigma, \Gamma, \delta', q_0', Z_0, F'>}}
\newcommand{\deltas}{\ensuremath{\hat{\delta}}}
\newcommand{\Cllamda}{\ensuremath{Cl_\lambda}}
\newcommand{\AFNDL}{\ensuremath{AFND-\lambda}}
\newcommand{\AFND}{\ensuremath{AFND}}
\newcommand{\AFD}{\ensuremath{AFD}}

\title{Teoria}
\author{}

\begin{document}
\maketitle
\tableofcontents

\section{Relaciones}
Relacion identidad: dos elementos estan relacionados solo si son el mismo. Es el
neutro de la composicion

Relacion potencia: $$R^0=id_A$$ $$R^{n+1} + R^N o R$$

Clausura transitiva: $R^+= \bigcup_{i=1}^{\infty}R^i$
Propiedades:
\begin{itemize}
 \item $R \subseteq R^+$: es trivial porque es una union de la que $R$ forma parte
 \item $R^+ $ es transitiva: como la union es infinita te podes armar la cadena
 que hace que la transitividad sea verdadera
 \item $R \subseteq G \wedge G$ es transitiva $ \Rightarrow R^+\subseteq G$: quiero
 ver que dos estados relacionados en $R^+$ lo estan en $G$. Si estan relacionados en
 $R^+$, entonces hay $k$ pasos de relacion en $R$, como $R \subseteq G$, vale esto
 mismo en $G$, y como esta ultima es transitiva, las puntas de esta secuencia estan
 relacionadas.
\end{itemize}

Clausura reflexo-transitiva: $R^+ \bigcup id_A$

\section{Lenguajes}
Concatenacion de lenguajes: $L_1L_2 = \{xy : x \in L_1 \wedge y \in L_2\}$
Potencia de lenguajes: como para relaciones, pero con la concatencion de lenguajes.
Clausura de Kleene: $L^*= \bigcup_{n \geq 0}L^n$
Clausura positiva: $L^+$ igual que la de kleene pero con $N \geq 1$. Se puede ver que 
$L^* = L^+ \cup \{\lambda\}$

\section{Gramaticas}
Forma sentencial: es una cadena de terminales y no terminales que es derivable.
Derivacion directa: en un paso
Lenguaje generado: Todas las formas sentenciales que son solo de terminales
\subsection{Tipos de gramaticas}
\begin{itemize}
	\item Regulares (tipo 3): Todas las producciones son a izquierda o a derecha, y 
	solo se permite un solo no terminal a la izquierda de cada produccion, y a lo sumo
	un no terminal a la derecha
	\item Independientes del contexto (tipo 2): Se relaja la restriccion de los no 
	terminales a la derecha de cada produccion y lo de las producciones a izquierda o 
	derecha
	\item Dependientes del contexto (tipo 1): Se relaja la condicion de que a la 
	izquierda solo pueda haber un solo no terminal. Solo se pide que la longitud
	de la parte izquierda de la produccion sea menor o igual que la de la parte derecha 
	\item Sin restriccion (tipo 0): sin restriccion
\end{itemize}

\section{Automatas}
\AFD: es una quintupla de $<Q, \Sigma, \delta, q_0, F>$. Cada cosa ya sabemos que es 
porque somos grandes. La funcion $\delta$ esta definda asi 
$\delta:Q\times\Sigma \rightarrow Q$.
Se extiende la funcion para que tome cosas de $\Sigma^*$ haciendo un fold sobre el
string. Si se le mete $\lambda$ a $\delta$ te quedas donde estas.

\AFND: idem que \AFD, salvo que $\delta:Q\times\Sigma \rightarrow P(Q)$.
Se puede extender esta funcion para que tome conjuntos de estados haciendo un
fold sobre el conjunto, y despues se la puede extender para que tome cadenas, 
haciendo un fold sobre la funcion que toma conjuntos. 

\subsection{Equivalencia entre \AFD y \AFND}
Es claro que la ida es trivial. Para la vuelta la 
idea de la demostracion es construir un AFD que tenga por estados tantos estados
como el conjunto de partes del conjunto de estados del AFND. Es importnte tener 
en cuenta que para definir la funcion de transicion del \AFD, se necesita la
funcion de transicion generalizada para conjuntos de estado del \AFND porque los
estados del \AFD son conjuntos de estados del \AFND. 

En general, para probar equivalencia de automatas, lo que se hace es ver
que la funcion de transicion generalizada de cada automata, para estados 
equivalentes y mismas cadenas, dan como resultado estados equivalentes 
(en el sentido de la demostracion de equivalencia) y despues con ese paso 
intermedio podes demostrar que los lenguajes
aceptados por los dos automatas son el mismo. El primer paso es por induccion en
el largo de la cadena, el segundo es por definicion (y usando el primero)

\AFNDL: Se define igual que el \AFND, salvo que ahora la $\delta$ puede tomar como
parametro $\lambda$ 

Clausura lambda: \Cllamda(q) es el conjunto de estados alcanzables tomando solo
transiciones lambda. Se extiende a conjuntos de estados haciendo un fold sobre
el conjunto.

En este caso la funcion de transicion extendida no es un simple fold:
$$\deltas(q, \lambda)= \Cllamda(q)$$
$$\deltas(q, xa)= \Cllamda(\bigcup_{r\in\deltas(q,x)}\delta(r,a))$$
Ojo que aca la funcion de transicion generalizada no generaliza porque en el 
caso base siempre mete una clausura lambda.

Nuevamente se extiende esta definicion a cconjuntos de estados haciendo un fold
sobre el conjunto

\subsection{Equivalencia entre \AFND y \AFNDL}
Equivalencia entre $\AFND M=\Automata$ y $\AFNDL M'= \AutomataPrima$.

Se define a 
\begin{equation*}
F' = \left\{
	\begin{array}{rl}
	   F \cup \{q_0\}& \text{si } \Cllamda(q_0) \cap F \ne \phi \\
		 F & \text{si no} \\
	\end{array} \right.
\end{equation*}

Nuevamente se prueba el paso intermedio de la funcion generalizada a traves de una
induccion en la cadena. Es importante tener en cuenta que para que todo funcione bien,
en el paso inductivo es necesario demostrarlo para la funcion que toma conjuntos de
estados. Una vez hecho este paso intermedo, partiendo en casos 
$x=\lambda \text{y } x \ne \lambda$, y en cada caso demostrando las dos inclusiones
sale por definicion. Notar que $q_0$ puede pertenecer a $F$ mas alla de que 
$\Cllamda(q_0)$ llegue o no a un estado final.

\subsection{Equivalencia entre gramaticas regulares y automatas regulares}
Dada una gramatica regular $G = \Gramatica \exists M=\Automata$, un automata no 
deterministico, equivalente. Nuevamente, la papa esta en la construccion:
\begin{itemize}
	\item $Q=V_n \cup \{q_f\}$
	\item $\Sigma = V_T$
	\item $q_0 = q_S$
	\item $q_B \in \delta(q_A, a) \Leftrightarrow A \rightarrow aB \in P$
	\item $q_f \in \delta(q_A, a) \Leftrightarrow A \rightarrow a \in P$
	\item $q_A \in F \Leftrightarrow A \rightarrow \lambda \in P$
	\item $q_f \in F$
\end{itemize}

Primero se demuestra esto, que sale usando induccion, y en el paso inductivo es
por definicion
$A \Rightarrow^* wB \Leftrightarrow q_B \in \delta(q_A,w)$

Y despues, teniendo cuidado con las produciones lambda, y partiendo en los casos de
cadena vacia y no vacia, se demuestra utilizando el lema anterior y la construccion
del automata. 

Para demostrar la vuelta, se lo hace para un $\AFD M=\Automata$. Se define la
gramatica de la siguiente forma:

\begin{itemize}
	\item $V_T = \Sigma$
	\item $S = A_{q_0}$
	\item $\produccion{A_p}{aA_q} \in P \Leftrightarrow \delta(p,a)=q$
	\item $\produccion{A_p}{a} \in P \Leftrightarrow \delta(p,a)=q \in F$
	\item $\produccion{S}{\lambda} \in P \Leftrightarrow q_0 \in F$
\end{itemize}

Primero se demuestra que $\delta(p, w) = q \Leftrightarrow \produce{A_p}{wA_q}$ 
y usando eso, que se demuestra por induccion en la cadena, se demuestra que los
lenguajes son equivalentes partiendo en casos (la cadena vacia, y no vacia).

\section{Indistinguibilidad y minimizacion de automatas}
Definicion de indistinguibilidad:
$$ q \equiv r \Leftrightarrow 
	\forall \alpha \in \Sigma^*,(
		\deltas(q,\alpha)\in F \Leftrightarrow \deltas(r,\alpha) \in F)$$
Se demuestra que esta relaion es de equivalencia (trivial porque se define a partir de
un si y solo si) y luego se demuestra que $\deltas$ respeta esta relacion (suponer
lo contrario lleva a un absurdo puesto que permite construir una cadena que distingue
los estados que por hipotesis eran indistinguibles)

Definicion: Dado un $\AFD M=\Automata$ sin estados inaccesibles, el \AFD minimo 
equivalente $M'=\AutomataPrima$ s define asi:
\begin{itemize}
	\item $Q'=Q/\equiv$
	\item $\delta'([q], a)= [\delta(q, a)]$
	\item $q_0'= [q_0]$
	\item $F'= \{[q]\in Q':q \in F\}$
\end{itemize}
luego se demuestra nuevamente que las funciones de transicion de los dos automatas 
respetan la relacion de equivalencia entre estados ($q=[q]$), es decir
$\deltas(q,\alpha) = r \Rightarrow \deltas'([q], \alpha)= [r]$
En este caso solo basta con esa implicacion. Nuevmente se demuestra por induccion en 
$\alpha$ y el paso inductivo es por definicion de la construccion.

Indistinguibilidad de Orden k:
$p\equiv^kq \Leftrightarrow \forall \alpha \in \Sigma^*(
	|\alpha \leq k| \Rightarrow (
			\deltas(p,\alpha)\in F \Leftrightarrow \deltas(q,\alpha) \in F))$ 

Propiedades:
\begin{itemize}
 \item $\equiv^k$ es una relacion de equivalencia. Trivial.
 \item $\equiv^{k+1}\subseteq\equiv^k$. Esto vale porque $\equiv^{k+1}$ habla de
 cadenas de longitud hasta $k+1$, y $\equiv^k$ lo hace hasta longitud $k$.
 \item $Q/\equiv^0=\{Q-F,F\} \text{ si } Q-F \ne \phi \wedge F \ne \phi$ 
 sale de la definicion de k-indistinguibilidad instanciando $k = 0$. Si 
 alguno de los conjuntos es vacio, simplemente no forma parte de la clase
 de equivalencia (i.e. no hay particion)
 \item $p\equiv{k+1}r \Leftrightarrow 
 			\forall a\in\Sigma \delta(p,a)\equiv^k\delta(r,a)$. Para la ida. Si vamos por
	el absurdo, existe $a$ que distingue a $\delta(p,a)$ de $\delta(r,a)$, por lo 
	que nos podemos armar una cadena de largo a lo sumo $k+1$ que distinga a $p$ de 
	$r$ empezando por $a$ y siguiendo con la que distingue a los $\delta(p,a)$ de
	$\delta(r,a)$. Para la vuelta se usa el absurdo tambien. Puesto que si no vale
	que $p$ y $r$ son k+1 indistinguibles, hay una cadena que los distinga. Notar
	que esta cadena tiene largo positivo, porque nunca $\lambda$ podria
	distinguir a $p$ de $q$ porque $k+1>0$. Entonces
	tomamos el primer caracter de esa cadena, y nos movemos por la transicion que
	corresponde. Entonces el resto de la cadena que tenemos distingue a los estados
	destino de la transicion, cosa que contradice la hipotesis.  
 \item $\equiv^{k+1} = \equiv^k \Rightarrow \forall n \geq 0 (\equiv^{k+n} = \equiv^k)$
 Este sale por induccion en $n$. El caso base es trivial. El caso inductivo es una 
 locura: Se quiere demostrar $\equiv^{k+n+1} = \equiv^k$. La idea es reescribir esto
 usando la propiedad anterior. Luego, se puede aplicar la H.I. a los $\delta(p,a)$. 
 luego se puede aplicar la propiedad anterior de nuevo, para convertir el predicado
 que habla de k-indistinguibilidad a k+1-indistinguibilidad, y por ultimo, utilizamos
 el antecedente del teorema, para concluir que $q\equiv^kr$
\end{itemize}

Lema: Sean dos \AFD M=\Automata, M'= \AutomataPrima, M no posee estados inaccesibles.
 $(\forall \alpha, \beta \in \Sigma^*, 
		\deltas(q_0, \alpha) \ne \deltas(q_0, \beta) \Leftrightarrow \Rightarrow
			\deltas(q'_0, \alpha) \ne \deltas(q'_0, \beta)) \Rightarrow |Q| \leq |Q'|$
Esta demostracion sale haciendo una funcion inyectiva entre $Q$ y $Q'$. Para eso
se define la funcion $g(q)= min \{\alpha\in\Sigma^*, \deltas(q_0,\alpha)= q\}$ y 
se demuestra que la funcion $f(q) = \deltas'(q'_0, g(q))$ es inyectiva. Eso sale
usando las hipotesis del teorema.

Lema: El automata $M_R$ correspondiente a $M= \Automata$ es mas chikito en 
cantidad de estados que cualquier otro automata $M'$ equivalente. La demostracion
sale por el absurdo y utilizando el contrareciproco del lema anterior. El hecho
de utilizarlo nos permite tener dos cadenas que van a dos estados distintos en el 
automata reducido y que van al mismo en $M'$.  Luego
se utiliza la el hecho de que en el automata reducido todos los estados son
distinguibles. De esta forma se llega a un absurdo porque se puede construir una
cadena que pertenece al lenguaje sii otra no pertenece en el automata reducido, y
en $M'$ pasa que esas dos cadenas o pertenecen las dos o no pertenece ninguna (por el
hecho de que los estados desde donde se parte son iguales).

\section{Lema de pumping para lenguajes regulares}
Lema: $(q,\alpha\beta) \vdash (q,\beta) \Rightarrow \forall in\geq0
					(q,\alpha^i\beta) \vdash (q, \beta)$
Sale por induccion en $i$.

Lema de pumping:
$\forall L \text{ regular }, \exists n, \forall z,$ 
$z\in L \wedge |z|\geq n \Rightarrow \exists u,v,w$
$z=uvw, n\geq|uv|,|v|\geq1 \wedge \forall i, uv^iw \in L$
La idea de la demostracion es considerar a un automata que reconozca este lenguaje, y 
tomar a $n$ como la cantidad de estados del automata. Entonces se agarra una cadena
que sea que sea mayor o igual que $n$ y se argumenta que tiene que haber dos estados
repetidos en la secuencia de estados por los se pasa al consumir la cadena. Entonces
se definen $k$ y $j$ como los indices de la sucesion de estados que se repiten y se 
define $u, v \text{ y } w$ asi ($m$ es el largo de $z$):
\begin{equation*}
u = \left\{
	\begin{array}{rl}
	   a_1 \hdots a_j & \text{si } j>0 \\
	   \lambda & \text{si no} \\
	\end{array} \right.
\end{equation*}
$$v = a_{j+1} \hdots a_k$$
\begin{equation*}
w = \left\{
	\begin{array}{rl}
	   a_{k+1} \hdots a_m & \text{si } k<m \\
	   \lambda & \text{si no} \\
	\end{array} \right.
\end{equation*}

\section{Expresiones regulares}
Dada una expresion regular, existe un \AFNDL con solo un estado final y sin 
transiciones salientes del mismo equivalente. La idea es ir armando recursivamente
el automata. Sale bastante straightforward

Dado un \AFD, existe una expresion regular equivalente. La idea de esta demostracion
es demostrar algo mas general, y es que para ciertos subconjuntos del lenguaje que
acepta el automata, existe una expresion regular. Luego a partir de estos subconjuntos
se construye el lenguaje uniendo algunos y por lo tanto se tiene la expresion regular.
Se define $R_{i,j}^k$ como el conjunto de las cadenas que van del estado $i$ al $j$
pasando por estados etiquetados con numero a lo sumo $k$ (los estados del automata
en esta demostracion empiezan de 1). Luego se define este conjunto recursivamente para
$k+1$ haciendo la union entre el conjunto de cadenas que pasan hasta $k$ y las
que pasan seguro por $k+1$: 
$$R_{i,j}^{k+1} = R_{i,k}^{k-1}(R_{k,k}^{k-1})^*R_{k,j}^{k-1}$$
Con esta definicion la demostracion por induccion re sale.

\section{Propiedades de lenguajes regulares}
Son cerrados con respecto a la union, y complementacion (eso es un conjunto adecuado
asi que tambien son cerrados con respecto al resto de las operaciones)

Para la complementacion, resulta que el automata que reconoce el complemento a un
lenguaje regular cambia solo en el conjunto de estados finales (es el complemento)

Para la union te construis el automata

\subsection{Problemas decidibles para lenguajes regulares}

Pertenencia: te construis el AFD y te fijas si acepta a la cadena
Finitud: Te fijas si hay adenas entre n y 2n, donde n es la cantidad de estados del
AFD.
Vacuidad: Ver si hay estados finales alcanzables desde el estado inicial del AFD
que reconoce el lenguaje.
Equivalencia: Se calcula $(L_1 \cap \bar{L_2}) \cup (\bar{L_1} \cap L_2)$ y se ve si
es vacio. Este conjunto es vacio sii $L_1 = L_2$ 

\section{Automatas de pila}
\subsection{Definiciones}
Un automata de pila M=\AutomataPila es:
\begin{itemize}
 \item $Q, \Sigma, q_0 \text{ y } F$ tienen la misma semantica que antes
 \item $\Gamma$ es el alfabeto de la pila
 \item $Z_0 \in \Gamma$ es el simbolo distinguido de la pila
 \item $\delta:Q\times(\Sigma \cup \{\lambda\})\times\Gamma \rightarrow 
 			\mathcal{P}(Q\times\Gamma)$
\end{itemize}

cambio de configuracion: 
$(q,a\alpha,t\pi)\vdash(r,\alpha,\tau\pi)$ si $(r,\tau) \in \delta(q,a,t)$
$(q,\alpha,t\pi)\vdash(r,\alpha,\tau\pi)$ si $(r,\tau) \in\delta(q,\lambda,t)$

Lema: Sea $G= \Gramatica$ una gramatica indeendiente de contexto con
$P \ne \phi$ y sea $\tau(S)$ un arbol de derivacion en $G$ para 
$\alpha$ cuya altura es $h$. Sea 
$a= max\{|\beta|:\produce{A}{\beta} \in P\}$ entonces $|\alpha| \leq a^h$

Sale por induccion en h.
Caso base: si $h=0$, el unico arbol de derivacion es el simbolo distinguido $S$. Entonces sale!
Caso inductivo: si $\tau(S)$ es de altura $h+1$. Sea $\alpha$ la base
del arbol, y sea $\gamma$ la base del arbol del arbol sacando el ultimo
nivel. Por HI $|\gamma| \leq a^h$ y ademas $|\alpha| \leq a |\gamma|$.

\subsection{Pumping para lenguajes independientes de contexto}
$\forall L \text{ indep. de context, } \exists n>0: \\
	\forall \alpha \in L,(|\alpha|\geq n \Rightarrow 
		\exists r,x,y,z,s: \alpha=rxyzs \wedge |xyz| \leq n
		\wedge |xz|>0 \wedge \forall i, rx^iyz^is \in L$

Demo: Sea $G$ una gramatica de tipo 2 y 
$a= max\{|\beta|:\produce{a}{\beta} \in P\}$. Sea $n=a^{|V_N| + 1}$. 
Por el lema anterior tenemos que $a^h \geq |\alpha|$ entones

$$a^h \geq |\alpha| \geq a^{|V_N| + 1} \Rightarrow h \geq |V_N| +1$$

Entonces existe un camino en el arbol de longitud superior a $|V_N|+1$.
Entonces se repite un no terminal. Sea $A$ el no terminal que se repite.
Recorriendo de forma ascendente este camino, sean $A_1$ y $A_2$ las
primeras dos apariciones del no terminal $A$ en este camino. Seguro
existe un $A$ tal que la distncia entre $A_2$ y la base sea menor que
$|V_N|+1$ (porque si no existe, entonces podemos elejir el no terminal
que se repite abajo de $A$ porque la distancia es mayor que $|V_N|+1$). $A_2$ genera xyz, entonces sabemos que 

$$ n=a^{|V_N|+1} \geq |xyz|$$

Sabemos que $|xz|>0$ porque si ambas fueran nulas podriamos armar un
arbol mas pequenho para $\alpha$.

Ahora tambien sabemos que \produce{A}{y} y que \produce{A}{xyz}
Entonces por induccion en la cantidad de veces que aparecen x y z 
podemos terminar de demostrar pumping.

Los lenguajes independientes de contexto son cerrados con respecto a:
\begin{itemize}
 \item la union (hago una gramatica con un simbolo distinguido con 
 produccionesque me lleven a los distinguidos de las gramaticas de 
 los lenguajes en cuestion). Es necesario que el conjunto de no 
 terminales de las dos gramaticas no se intersequen.
 \item la concatenacion: concateno los simbolos distinguidos
 \item clausura positiva: hago dos producciones que generen el
 simbolo distinguido tantas veces como quiera
\end{itemize}

con respecto a la interseccion no son cerrados. La idea es intersecar
dos lenguajes independientes de contexto y que la interseccion de 
$\{a^nb^nc^n:n\geq 0\}$

Teo: El lenguaje $L= \{ww : w\in \Sigma^*\}$ no es independiente de
contexto. El lenguaje $L_1= \{a^nb^ma^nb^m:n,m\geq 0\}$ no es
independiente de contexto. Ademas $L_1 = L \cap a^*b^*a^*b^*$.
Como la interseccion entre un lenguaje regular con uno independiente
de contexto es independiente de contexto, resulta que $L$ no puede
ser independiente de contexto.

Teo: si $M= \AutomataPila$, entonces existe una gramatica 
$G= \Gramatica$ libre de contexto que genera el lenguaje 
$L_\lambda(M)$.

\begin{itemize}
	\item $V_N = \{[q,A,p] : q\in Q, A\in \Gamma, p \in Q \cup \{S\}\}$
	\item $V_T = \Sigma$
	\item $S \notin \Gamma$
	\item 
		\begin{enumerate}
			\item $\produccion{S}{[q_0,Z_0,q]} \forall q \in Q$
			\item $\produccion{[q,A,q_{m+1}]}
						{a[q_1,B_1,q_2]\hdots[q_m,B_m,q_{m+1}]}$ si 
						$(q_1,B_1,\hdots,B_m)\in \delta(q,a,A)$
			\item $\produccion{[q,A,q_{m+1}]}
						{[q_1,B_1,q_2]\hdots[q_m,B_m,q_{m+1}]}$ si 
						$(q_1,B_1,\hdots,B_m)\in \delta(q,\lambda,A)$
			\item $\produccion{[q,A,q_1]}{a}$ si $(q_1,\lambda) 
						\in \delta(q,a,A)$
			\item $\produccion{[q,A,q_1]}{\lambda}$ si 
						$(q_1,\lambda)\in\delta(q,\lambda,A)$
		\end{enumerate}
\end{itemize}

La idea de esta gramatica es que genera todas los posibles caminos
desde $q_0$ que respetan la funcion de transicion. Y la idea es que
$[q,A,p]$ genera la cadena que el automata aceptaria si arranca desde el estado $q$ con la pila en $A$ y forzando que termine en el estado $p$.
En las producciones, observar que el $m$ lo determina $\delta$ diciendo
cuantos simbolos se apilan. Es importante notar tambien
que una derivacion en esta gramatica puede terminar, si la codificacion
del no terminar correspondiente concuerda con la funcion de transicion.
Los estados subindicados, son cualesquiera; se subindican porque 
se necesitaban muchas letras.  Lo que queremos probar es entonces que

$$[q,A,p] \Rightarrow^*_G x\text{ sii }(q,x,A)
			\vdash^*_M(p,\lambda,\lambda)$$ 

Para demostrar esto se hace lo siguinte:
\begin{enumerate}
	\item Demostrar que todo lo que acepta el automata desde algun estado
	es generdo por la gramatica. 
	$\forall i (q,x,A) \vdash^i_M (p,\lambda,\lambda)
	\Rightarrow [q,A,p]\Rightarrow^*_G x$
	\item Demostrar que si algo es generado por la gramatica, entonces
	es aceptado por el automata desde el estado correspondiente, y no
	solo eso sino que termina donde dice la tercer coordenada del
	no terminal. $\forall [q,A,p]\Rightarrow^i_G x \Rightarrow
			(q,x,A)\vdash^*_M(p,\lambda,\lambda)$
	\item Ver que el hecho de que la gramatica funciona es un caso
				particular de lo recien demostrado
\end{enumerate}

Paso 1: Sale por induccion en $i$. Para $i=0$ es porque $x=a$ o 
$x=\lambda$. El desarrollo es sencillo y la demostracion por
construccion. Sale.

Caso inductivo. Nadie dice que $x$ no puede ser $\lambda$, y es
por esto que se parte en dos casos que no son disjuntos solo
para aliviar la notacion: $x=ay \lor x=y, y\in\Sigma^*$. Entonces
puede pasar alguna de las sguientes cosas:

$$ (q,ay,A) \vdash_M (q_1,y,B_1\hdots B_n) \vdash^{i-1}_M (p,\lambda,\lambda)$$
$$ (q,y,A) \vdash_M (q_1,y,B_1\hdots B_n) \vdash^{i-1}_M (p,\lambda,\lambda)$$

Como el automata acepta por pila vacia, podemos descomponer a la cadena
$y$ en subcadenas $y_1, \hdots, y_n$ donde $y_j$ es tal que la cadena
$y_1,\hdots,y_j$ hace que el simbolo $B_{j+1}$ quede en el tope
de la pila por \emph{primera} vez.
Entonces, por la definicion de los $y_j$, existen estados 
$q_1, \hdots, q_{n+1}$ tales que
$$(q_j,y_j,B_j) \vdash^*_M (q_{j+1}, \lambda, \lambda)$$. 

Esto se hace en menos de $i$ transiciones, es por eso que podemos 
aplicar la hipotesis inductiva y llegar a que 
$[q_j,B_j,q_{j+1}] \Rightarrow^*y_j$.

Ahora, por las producciones 2 y 3 y por lo que acabamos de concluir, 
podemos decir que $[q,A,q_{m+1}] \Rightarrow^*x$

Paso 2: Ahora veamos la vuelta. Nuevamente se hace induccion en la
cantidad de pasos de la derivacion. La demostracion es muy parecida
a la otra, asi que n la voy a hacer.

Paso 3: Si instanciamos algunas cosas nos queda que
$[q_0, Z_0, p] \Rightarrow^*_G x \Leftrightarrow 
		(q_0, x, Z_0) \vdash^*_M (p, \lambda, \lambda)$. Lo cual es 
equivalente a decir que los lenguajes son iguales.

Teo: Para todo APD M= \AutomataPila, existe otro APD M' equivalente
que consume toda la cadena.
Este teorema es nesario para ver como calcular el automata complemento, 
porque como el automata es deterministico, podria colgarse en un
ciclo de transiciones lambda. Tambien podria "trabarse" (i.e. ninguna
transicion es posible, cosa que tambien pasa con los otros.)

Bueno, entonces la idea es construir un automata 
$ M'=<Q\cup\{q_0',d,f\},\Sigma,\Gamma\cup\{X_0\},\delta',q_0',X_0, F\cup\{f\}>$ 
donde:
\begin{itemize}
	\item $\delta'(q_0',\lambda,X_0) = (q_0, Z_0X_0)$

	\item $\forall q\in Q, a\in\Sigma,Z\in\Gamma,$
	$$\delta(q,a,Z)=\delta(q,\lambda,Z)=\phi
						\Rightarrow\delta'(q,a,Z)=(d,Z)$$, y
	$$\forall q\in Q, a\in\Sigma,\delta'(q,a,X_0)=(d,X_0)$$

	\item $\forall a\in\Sigma,Z\in \Gamma\cup\{X_0\},\delta'(d,a,Z)=(d,Z)$

	\item si hay un loop lambda (esta es una forma bizarra de escribirlo
	para $q\in Q, Z\in\Gamma$ pasa que
	$$\forall i>0\exists q_i,\gamma_i, \text{ para los cuales }
			(q,\lambda,Z)\vdash^i(q_i,\lambda,\gamma_i)$$, Entonces, si
			ningun $q_i$ es final, entonces $\delta'(q,\lambda,Z)=(d,Z)$. Si
			no $\delta'(q,\lambda,Z)=(f,Z)$

	\item $\forall Z\in\Gamma\cup\{X_0\} \delta'(f,\lambda,Z)=(d,Z)$

	\item $\forall q\in Q,a\in\Sigma\cup\{\lambda\},Z\in\Gamma \text{
		si } \delta'(q,a,Z) \text{ no fue definida en los items
		anteriores, entonces } \delta'(q,a,Z)=\delta(q,a,Z)$
\end{itemize}

Luego, la "demostracion" es por el absurdo.

Teo: El complemento de un lenguaje independiente de contexto
deterministico es independiente de contexto deterministico.
La idea es tener 3 planos. Son finales los estados del tercer plano.
En el segundo plano se puede estar solo si el estado actual no es
final, y en el plano un se esta cuando el estado actual es final.
Ademas del segundo plano se pasa por transiciones lambda al tercer
plano, por lo que si se termino la cadena y no estoy en un estado
final, entonces estoy en el plano 2, entonces puedo ir por transicion
lambda al plano 3, y voila!. Notar que como el automata tiene que
quedar deterministico, en el plano 2 no se consume entrada, solo en
los planos 1 y 3.

\subsection{Simbolos activos y alcanzables}
Dada una cierta gramatica, se dice que un simbolo $A\in V_N$ es
alcanzable si $\produce{S}{\alpha A\beta}$

$A$ es activo sii $\produce{A}{\alpha}$

$A$ es util sii es alcanzable y activo.

el algoritmo para obtener el conjunto de los simbolos activos me da
paja escribirlo. Pero la idea es que onsiste en ver si la parte
derecha de cada produccion de la gramatica pertenece a 
$(Act \cup V_T)^*$, donde Act es el conjunto de los activos. Eso se
repite hasta que Act no cambie

El algoritmo para construir el conjunto de los simbolos anulables, se
inicializa el conjunto en los no terminales que tienen una produccion
a $\lambda$ y despues se agrega todos los que tienen una produccion a
la clausura del conjunto.
\end{algoritmo}

\section{Maquinas de Turing}
Una maquina de turing es un automta definido por M=\MaquinaTuring.
Es todo igual salvo que $\Gamma$ es el conjunto de simbolos de la
cinta, $B \in \Gamma$, y representa al blanco, y 
$\delta:Q\times\Gamma \rightarrow Q \times\Gamma\times\{L,R\}$. Por
ultimo, y no menos importante $\Sigma \subseteq \Gamma$


La configuracion instantanea esta dada por $\alpha_1q\alpha_2$ donde
estas cadenas representan lo que esta a la izquierda y a la derecha de
la cinta hasta el simbolo distinto de B mas a la derecha. Si el
simbolo inmediato siguiente a la cabeza es B, entones es $\lambda$

El lenguaje aceptado por una maquina de turing es:
$$\{w:w\in\Sigma^* \text{ y } q_0w\vdash\alpha_1p\alpha_2, p\in F,
\alpha_1,\alpha_2\in\Gamma^*\}$$. La maquina de turing no tiene
transiciones salientes de los estados finales.

\subsection{Equivalencia entre maquina de turing deterministica y no deterministica}
La idea es si $m$ es el grado del nodo de mayor grado
de transiciones salientes, entonces la idea es generar todas las
secuencias de numeros en base $m$. Tenemos 3 cintas, la primera tiene
la entrada (y no se toca), la segunda es donde guardamos estos numers
en base $m$ y la tercera la usamos para simular la maquina de turing
no deterministica

\subsection{Equivalencia entre gramatias sin restricciones y maquinas
de turing}
Dada una gramatica de tipo 0, existe una maquina de turing
equivalente. Se construye una maquina de turing no deterministica con
dos cintas, la primera tiene a w, y la segunda tiene formas
sentenciales. Se comienza por el simbolo distinguido $S$, y luego se
elije no deterministicamente producciones que sirvan para reemplazar
algo en la segunda cinta. En cada paso se verifica si la cadena de la
segunda cinta es igual a la de la primera cinta.

Dada una maquia de turing, existe una gramatica sin restricciones. La
gramatica se define asi: $V_T=\Sigma$,
$V_N=((\Sigma\cup\{\lambda\})\times\Gamma) \cup \{A_1,A_2,A_3\}$ 
y el conjunto de producciones
\begin{itemize}
	\item $\produccion{A_1}{q_0A_2}$
	\item $\produccion{A_2}{[a,a]A_2}\forall a\in\Sigma$
	\item $\produccion{A_2}{A_3}$
	\item $\produccion{A_3}{[\lambda,B]A_3}$ Esta produccion es para
	hacer lugar para que la maquina de turing labure tranquila
	\item $\produccion{A_3}{\lambda}$
	\item $\produccion{q[a,X]}{[a,Y]p}\text{ si } \delta(q,X)=(p,Y,R)$
	\item $\produccion{[b,Z]q[a,X]}{p[b,Z][a,Y]}\text{ si } 
		\delta(q,X)=(p,Y,L)$
	\item $\produccion{[a,X]q}{qaq}, \produccion{q[a,X]}{qaq},
	\produccion{q}{\lambda} \text{ si } q\in F$
\end{itemize}

Ahora, mediante las reglas 1 y 2 se pueden generar dos copias de la
cadena, y luego se puede demostrr que si la maquina de turing avanza
en su configuraccion instantanea, la gramatica genera una forma
sentencial equivalente(en el sentido de que hay las mismas cosas en la
inta que no terminales en la forma sentencial, y que el estado esta en
la misma posicion en ambos lados). Esta demostracion, como siempre es
en la cantidad de transiciones. El caso base es con $i=0$ por lo que
es trivial. El caso inductivo sale por cconstruccion (logicamente :))

\subsection{Maquinas de turing linealmente acotadas}
Una maquina de turing linealmente acotada tiene dos simbolos
distinguios dentro de su alfabeto que delimitan el espacio de trabajo,
puesto que el cabezal de la maquina no se puede mover ni a la
izquierda del tope izquierdo ni a la derecha del tope derecho.

Si $L$ es un lenguaje dependiente del contexto, entonces existe una
maquina de turing linealmente acotada que lo reconoce. La maquina es
muy parecida a la que se utiliza para las gramaticas sin
restricciones. Primero se fija si $w$, la cadena de entrada, es
$\lambda$; si es asi, la rechaza. Luego elije una produccion que pueda
aplicar no deterministicamente, la aplica y se fija si la nueva forma
sentencial es mayor en su longitud que $w$. En ese caso tambien
rechaza (porque las producciones de este tipo de gramaticas hace que
las formas sentenciales sean crecientes en su longitud). Por ultimo se fija si la forma sentencial generada es $w$, si
no, sigue con el procedimiento.

\subsection{Un poco de computabilidad}
Es claro que los lenguajes dependientes de contexto son recursivos
(teniendo la gramatica), pues saber si una cadena pertenece o no, se
reduce a hacer reachability en un grafo donde los nodos son las
cadenas de terminales y no terminales de longitud hasta $|w|$. Dos
nodos estan relacionados sii existe una produccion que transforma la
cadena del nodo origen en la cadena del nodo destino.

Si $M_1, M_2, \hdots$ es una enumeracion de todas las maquinas de
turing que parane n todas las entradas, utilizando el argumento
diagonal se puede demostrar que hay un lenguaje recursivo que no es
aceptado por ninguna de ellas.

Como demostramos que las gramaticas dependientes de contexto son
recursivas, utilizando el lema anterior podemos llegar a que existe un
lenguaje que es recursivo y no es dependiente de contexto.

Consideremos a las maquinas de turing sobre $\{0,1\}^*$. Es posible
codificarlas de la siguiente manera: Primero codigificamos las
transiciones $\delta(q_i,X_j)=(q_k,X_l,D_m)$ como
$0^i10^j10^k10^l10^m1$ y despues separamos cada una de estas con un
separador que sepamos que no aparece en ninguna transicion, como
$111$. En esta codificacion el estado inicial es $q_1$ y el final es
$q_2$. Por ultimo, como esta codificacion no es biyectiva, cualquier
secuencia de ceros y unos que no corresponda a una maquina de turing
mediante la representacion anterior, corresponde a una maquina que
acepta el lenguaje vacio :).

Utilizando esta codificacion se puede ver que existe un lenguaje que
no es recursivamente enumerable. Se define 
$L_d=\{w_i:w_i\notin L(M_i)\}$ Donde $w_i$ es la iesima cadena en
orden lexicografico. Suponer que este lenguaje es recursivo lleva a un
absurdo en un paso.

Se define al lenguaje universal como $L_u=\{<M,w>:w\in L(M)\}$

El lenguaje universale es recursivamente enumerable.
Se construye una maquina de turing de 3 cintas. La primera corresponde
a la entrada, es decir, la maquina de turing y la cadena. La segunda
simula la cinta de la maquina que esta codificada en la cinta 1, y la
tercera se usa para guardar el estado. Luego lo que se hace es revisar
que sea una codificacion valida lo que esta en la cinta 1, y ademas
que la maquina sea deterministica. Luego lo que se hace es simular la
maquina. Solo se acepta si el contenido de la cinta 3 es $00$ que
corresponde al estado $q_2$.

El lenguaje universal no es reursivo pueso que si lo fuera, podriamos
construir un algoritmo para reconocer al complemento de $L_d$, y por
lo tanto a $L_d$ que no es recursivamente enumerable.

\subsubsection{Teorema de Rice}
Toda propiedad no trivial de los lenguajes r.e. no es
deicidible. Sea $S$ tal que $\psi \notin S$. Como $S$ es una propiedad
no trivial, existe un lenguaje $L$ en $S$. Notar que como $L$ es r.e, 
existe una maquina de turing que acepta a ese lenguaje.

Para demostrar el teorema vamos por el absurdo. Supongamos que
$S$ si es decidible. Entonces existe una maquina de turing $M_S$ que
acepta $<M>$ solo cuando $L(M) \in S$. Entonces se puede construir un
algoritmo que para cada $<M>$, $w$ nos de el codigo de una maquina
$M'_{M,w}$ de forma tal que que si $w \in L(M)$ devuelva el lenguaje
$L$ y si no devuelva el lenguaje $\psi$. Entonces utilizando $M_S$
podemos determinar si $L(M'_{M,w}) \in S$ lo cual equivale a ver que
$<M,w> \in L_u$. Absurdo puesto que $L_u$ no es decidible.

\section{Parsers}
\subsection{Parsers decendentes}
En la materia se dan 3. Por un lado el parser con retroceso
(backracking) que basicamente es el automata que se construye en la
demostracion de que para una gramatica libre de contexto existe un
automata de pila no deterministico. 

El siguiente parser que se ve es el parser predictivo, y el predictivo
con tabla, que es igual que el predictivo salvo por como se guarda la
informacion.

\subsection{Parsers descendentes predictivos}
Antes de empezar, es necesario contar con las siguientes definiciones.
$V=V_T \cup V_N$
$Primeros_k:V^* \rightarrow P(V_T)$
$Primeros_k(\gamma)=\{x\in V_T^* : (\produce{\gamma}{x\alpha} \wedge
|x| = k) \lor (\produce{\gamma}{x} \land |x| < k)\}$

$Siguientes:V_N \rightarrow P(V_T)$
$Siguientes(N)=\{x:x\in V_T^* \land \produce{S}{\hdots Nx\hdots} \land
|x| \leq k\}$

\begin{equation*}
$SD_k(\produccion{A}{\alpha}) = \left\{
	\begin{array}{rl}
	   Primeros_k(\alpha)& \text{si } \alpha \text{ no es anulable} \\
	   Primeros_k(\alpha) \cup Siguientes_k(A) & \text{si no} \\
	\end{array} \right.
\end{equation*}

Se dice que un lenguaje es LL(k) si $\forall \produccion{A}{\alpha},
\produccion{A}{\beta}, \alpha\ne\beta \Rightarrow
SD_k(\produccion{A}{\alpha}\cap SD_k(\produccion{A}{\beta}) = \psi$

Si un lenguaje es LL(1) para parsearlo, lo que hay que hacer es, en
ell procedimiento para elejir como expandir un no terminal dado,
fijarse a que parte derecha de las producciones de ese no terminal
pertenece el look ahead y usar esa produccion. 

El parser predictivo con tabla en lo que difiere es que tiene una
tabla de doble entrada, una entrada es para los no terminales y otra
para el look ahead, y en la posicion dada dice la produccion que debe
utilizarse en base a los simbolos directrices, o error si no hay nada.
La entrada viene delimitada con el simbolo \$ y se cuenta con una pila
que se inicializa con el simbolo \$ y con el simbolo distinguido de la
gramatica. Luego el algoritmo es bastante obvio.

Una gramatica ampliada, es una gramatica a la que se le agrega un
nuevo no terminal $S'$, que reemplaza al simbolo distinguido, y cuya 
unica produccion es $\produccion{S'}{S#}$

Una gramatica reducida es una gramatica en la que todos los no
terminales son utiles.

Lema: Sea G una gramatica ampliada y reducida (que trabalenguas!),
entonces $\forall U \in V_N, Siguientes(U) \ne \psi$. La idea de por
que esto es verdadero es que al menos esta # en Siguientes.

Teorema: Para toda gramatica reducida, que es LL(1), no puede ser
recursiva a izquierda.
La demostracion no me queda en claro...
%Demostracion: Supongamos que tenemos una gramatica que cumple con las
%hipotesis y ademas es recursiva a izquierda. Como es recursiva a
%izquierda, existe un no terminal $A$ tal que $\produce{A}{A\alpha}$
%con $\alpha \in V^+$. Notar que como la gramatica es recursiva a
%izquierda, el lenguaje generado es infinito. Entonces existe $x$ tal
%que en su derivacion aparece mas de una vez el no terminal $A$ (porque
%la gramatica es reducida). Sea $A$ el ultimo no
%treminal que se repite. Como esa es la ultima aparicion de este no
%terminal, la produccion utilizada, tiene que se distinta a la
%produccion utlizada 

\section{Parsers LR}
\subsection{Algunas definiciones}
Pivote: Sea $\gamma=\alpha\rho\beta$ una forma sentencial derecha(fsd),
entonces $\rho$ es pivote de $\gamma$ si $\exists \produccion{N}{\rho}
\in P$, tal que si reemplazamos $\rho$ por $N$ en
$\gamma$, vayamos un paso atras en la derivacion mas a la
derecha. Notar que si $\rho$ es privote, entonces $\beta\in
V_T^*$

Prefijo viable: Sea $\alpha\rho\beta$ un fsd, donde $\rho$ es pivote,
entones $\gamma$ es prefijo viable si es prefijo de $\alpha\rho$

Item: Es una produccion con un punto en alguna parte del lao derecho.
Si el lado derecho de la produccion es $\lambda$ hay un solo item.

Item valido: Un item $\produccion{A}{\beta_1.\beta_2}$ es valido para
un prefijo viable $\alpha\beta_1$ si
$\produceD{S}{\produceD{\alpha Aw}{\alpha\beta_1\beta_2 w}}$

\subsection{Parser LR abstracto}
Tenemos una pila donde contenemos simbolos de la gramatica, y un
buffer para la entrada. La pila tiene en el tope el simbolo \$, y la
cadena tiene al fondo tambien este simbolo. El parser en cada paso
decide si aceptar la cadena, dar error, reducir o desplazar. El parser
desplaza una cierta cantidad de simbolos a la pila hasta que en el
tope queda un pivote. En ese momento reduce el pivote al no terminal
correspondiente. Este procedimiento se repite hasta que el parser
detecte un error, o hasta que el buffer quede solo con el simbolo \$ y
la pila con \$S donde S es el simbolo distinguido.

Notar que una gramatica ambigua nunca puede ser LR puesto que de ser
asi, existiria una cadena que tenga mas de un pivote por lo que el 
parser no sabria que hacer.

\subsection{Notas de implementacion}
En un parser LR, lo unico que cambia es la tabla de parser. El resto
es todo igual. La pila contiene una secuencia de $s_0X_1\hdots X_ns_n$
donde $s_n$ esta al tope de la pila. Cada $X_i$ es un simbolo de la
gramatica, y cada $s_i$ es un simbolo llamado estado. Estos simbolos
de estado resumen la informacion de lo que esta en la pila detras de
el.

\subsection{Parsers SLR}
algoritmo para la construccion de la tabla: pagina 227 libro del dragon

\subsection{Parser canonico LR}
pagina 230 del libro del dragon
\end{document} 

